#include <stdlib.h>
#include <stdio.h>

//定义一个结构体
typedef struct node {
    //编号
    int number;
    //节点指向
    struct node *next;
} person;

//初始化一个首尾相连的链表
person *initTable(int n) {
    person *temp = (person *) malloc(sizeof(person));
    temp->number = 1;
    temp->next = NULL;

    person *head = temp;
    for (int i = 2; i <= n; ++i) {
        person *new_node = (person *) malloc(sizeof(person));
        new_node->number = i;
        new_node->next = NULL;
        temp->next = new_node;
        temp = new_node;
    }

    //使链表首尾相连
    temp->next = head;

    return head;
}

void displayTable(person *link) {
    person *temp = NULL;
    int i = 0;
    while (link && link != temp) {
        i++;
        if (i == 1) {
            temp = link;
        }
        printf("%d ", link->number);
        link = link->next;
    }
    printf(" \n");
}

//head是头指针。从k开始数数，并让数到m的人出局。依次循环，直到最后一个人就是胜者。
void findAndOut(person *head, int k, int m) {
    //首先找到最后一个节点
    person *tail = head->next;
    while (head != tail->next) {
        tail = tail->next;
    }

    //找到k的位置
    person *start = head;
    while (start != tail) {
        if (start->number == k) {
            break;
        }
        start = start->next;
    }
    if (start->number != k) {
        printf("没有找到编号为 %d 的人！", k);
        return;
    }


    while (start->next != start) {
        person *temp = start;
        for (int i = 2; i < m; ++i) {
            temp = temp->next;
        }

        person *out = temp->next;

        //把temp指向的节点干掉
        temp->next = out->next;
        printf("出局的人: %d\n", out->number);
        //释放
        free(out);

        //下一个节点继续
        start =  temp->next;
    }

    printf("最后一个出局的人： %d",start->number);
    free(start);

}

void findAndKillK(person * head, int k, int m) {
    person * p = NULL;
    person * tail = head;
    //找到链表第一个结点的上一个结点，为删除操作做准备
    while (tail->next != head) {
        tail = tail->next;
    }
    p = head;
    //找到编号为k的人
    while (p->number != k) {
        tail = p;
        p = p->next;
    }
    //从编号为k的人开始，只有符合p->next==p时，说明链表中除了p结点，所有编号都出列了，
    while (p->next != p) {
        int i = 0;
        //找到从p报数1开始，报m的人，并且还要知道数m-1de人的位置tail，方便做删除操作。
        for (i = 1; i < m; i++) {
            tail = p;
            p = p->next;
        }
        tail->next = p->next;//从链表上将p结点摘下来
        printf("出列人的编号为:%d\n", p->number);
        free(p);
        p = tail->next;//继续使用p指针指向出列编号的下一个编号，游戏继续
    }
    printf("出列人的编号为:%d\n", p->number);
    free(p);
}

int main() {
    int n = 6;
    person *head = initTable(n);
    displayTable(head);
    findAndOut(head, 2, 2);
//    findAndKillK(head,2,3);
    return 0;
}
